package com.yinxin.wudasuanfa.sort;

import java.util.Arrays;

/**
 * @author yinxin
 * @version 1.0
 * @Description: 计数排序(通过计数而不是比较来排序，适用于范围较小的整肃序列)
 * @date 2022/4/1817:08
 */
public class CountingSort {
    public static void main(String[] args) {
        int[] arr = {2,4,1,2,5,3,4,8,7};
        countSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 计数排序
     * @param arr 数组
     */
    private static void countSort(int[] arr) {
        //1、找最大值
        int max=arr[0];
        for (int num : arr) {
            if(num>max){
                max=num;
            }
        }
        //2、计数数组：并初始化为0，记录每个数出现的次数，index为这个数
        int[] countTmp = new int[max+1];
        for (int num : arr) {
            countTmp[num]++;
        }
        System.out.println("Arrays.toString(countTmp) = " + Arrays.toString(countTmp));
        //3、累计数组：记录数组中每个元素出现的位置
        int[] addTmp = new int[max+1];
        for (int i = 0; i < countTmp.length; i++) {
            addTmp[i]+=countTmp[i];
        }
        System.out.println("Arrays.toString(addTmp) = " + Arrays.toString(addTmp));
        //4、输出最终结果
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < addTmp.length; j++) {
                if(addTmp[j]!=0){
                    for (int k = 0; k < addTmp[j]; k++) {
                        arr[i++]=j;
                    }
                }
            }
        }
    }
}
